This disclosure relates generally to the field of error correction in a communication system, and in particular, to a method and apparatus for encoding using low density parity check (LDPC) codes.
In communication systems, the link performance is affected by various noises in channels, a fading phenomenon, and Inter-Symbol Interference (ISI). Therefore, in order to realize high-speed digital communication systems requiring high data throughput and reliability, such as in the 60 GHz personal area network (PAN), next-generation mobile communication, digital broadcasting, and portable internet, it is advantageous to develop a technology for operating in the presence of noise, fading and ISI. Error-correcting codes are typically used for increasing communication reliability by efficiently recovering distorted information.
Low density parity check (LDPC) codes are used for error correcting in noisy channels and appear in various wireless and wired standards. LDPC codes are linear block codes, and as such, can be represented by a parity check matrix. LDPC codes are low density parity check codes, which means that their parity check matrix is sparse. A sparse matrix has very few non-zero entries. Systematic LDPC codes are codes such that the information symbols are an explicit part of the codeword.
Quasi-cyclic (QC) LDPC matrices are common as they can be concisely described. An example for QC LDPC matrix (binary rate ½ LDPC code, with Z=28) is shown in FIG. 1. The code rate represents the ratio of information to parity bits. For the ½ rate example above, half of the bits of a codeword are information bits and the other half are parity check bits. A “−1” entry in the matrix represents a Z×Z matrix having all zeros. Each other entry in this matrix represents a permutation matrix of size Z×Z. Thus, if the exemplified matrix has 24 columns and if Z=28, then this matrix is associated with a 28*24=672 bit code. A permutation matrix is a matrix that has a single “1” in each row and a single “1” in each column. For example, the matrix as shown in FIG. 2 is a 8×8 permutation matrix. Moreover, the exemplified permutation matrix is a cyclic permutation matrix. The QC LDPC is made of cyclic permutation matrices. An entry that is not “−1” is the amount of cyclic permutation of the submatrix.
The present disclosure holds for LDPC codes defined over any Galois field, but for brevity and better insight, the discussion and examples of the present disclosure are confined to Galois field of size 2, meaning the binary field. When LDPC codes over other fields are considered, the main properties required by this disclosure remain the same, which are the following: the matrix structure after reordering and the invertibility of sub-matrix D, described below.